package com.example.Arithmetic.Arithmetic;

import com.example.Arithmetic.Arithmetic.Port.Priority;
import com.example.Arithmetic.Arithmetic.Port.Queue;

/**
 * 日期：2023/10/10
 * 时间：10:16
 * 描述：优先级队列，无序数组实现
 */
public class PriorityQueueDisorderArray<E extends Priority> implements Queue<E> {
    Priority[] array;
    int size;

    public PriorityQueueDisorderArray(int capacity) {
        array = new Priority[capacity];
        size = 0;
    }

    @Override
    public boolean offer(E value) {
        if (isEmpty()) {
            return false;
        }
        array[size++] = value;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        int i = SelectMax();
        E priority = (E) array[i];
        Remove(i);
        return priority;
    }

    //    删除元素
    private void Remove(int i) {
        if (i < size - 1) {
            System.arraycopy(array, i + 1, array, i, array.length - i - 1);
        }
        array[size--] = null;     //help GC
    }

    //    寻找最大索引
    private int SelectMax() {
        int max = 0;
        for (int i = 1; i < size; i++) {
            if (array[i].priority() > array[max].priority()) {
                max = i;
            }
        }
        return max;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[SelectMax()];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
